L2-016 愿天下有情人都是失散多年的兄妹

题目 L2-016 愿天下有情人都是失散多年的兄妹

image-661990f2

思路分析

image-bc2a2773

使用邻接表把所有的关系存起来 查询时使用dfs把双方五代全部进行标记 如果有重复的 就说明找到了公共祖先 不能通婚

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=1e5+10;
vector<int> v[N];
char gender[N];
bool isFound=false;
bool st[N];

void dfs(int u,int depth){
	if(depth>=5)	return;
	if(st[u]){
		isFound=true;
		return;
	}
	st[u]=true;
	for(auto parent : v[u]){
		dfs(parent,depth+1);
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	while(n--){
		int curId,fatherId,motherId;
		char curGender;
		cin>>curId>>curGender>>fatherId>>motherId;
		gender[curId]=curGender;
		if(fatherId!=-1){
			gender[fatherId]='M';
			v[curId].push_back(fatherId);
		}
		if(motherId!=-1){
			gender[motherId]='F';
			v[curId].push_back(motherId);
		}
	}

	int k;cin>>k;
	while(k--){
		int x,y;cin>>x>>y;
		isFound=false;
		memset(st,false,sizeof st);
		dfs(x,0);
		dfs(y,0);
		if(gender[x]==gender[y])	cout<<"Never Mind"<<endl;
		else{
			if(!isFound)	cout<<"Yes"<<endl;
			else	cout<<"No"<<endl;
		}
	}

	return 0;
}

同类题型

视频讲解

⬅️ L2-015 互评成绩 🏠 00-天梯赛 ➡️ L2-017 人以群分